Sophia's Learning Journal

Minimum Window Substring

Sliding window. Expand right unconditionally, shrink left while the window is valid. Track character frequencies for both s and t. Update the shortest window inside the shrink loop.

Approach 1 — Simple (easier to understand): check validity with all(s_freq[c] >= t_freq[c] for c in t_freq) — O(|t|) per iteration.

t_freq = defaultdict(int)
s_freq = defaultdict(int)
for c in t:
    t_freq[c] += 1

shortest = ""
left = 0

for right in range(len(s)):
    s_freq[s[right]] += 1

    while all(s_freq[c] >= t_freq[c] for c in t_freq):
        valid_substring = s[left:right+1]
        if not shortest or len(shortest) > len(valid_substring):
            shortest = valid_substring
        s_freq[s[left]] -= 1
        left += 1

Approach 2 — Optimized with have / need: instead of checking all characters each iteration, track how many distinct characters have met their frequency threshold. Validity becomes O(1).

need = len(t_freq). Increment have when s_freq[c] reaches t_freq[c] after adding. Decrement have when s_freq[c] drops below t_freq[c] after removing.

need = len(t_freq)
have = 0
left = 0
shortest = ""

for right in range(len(s)):
    added_char = s[right]
    s_freq[added_char] += 1
    if s_freq[added_char] == t_freq[added_char]:
        have += 1

    while have == need:
        valid_substring = s[left:right+1]
        if not shortest or len(shortest) > len(valid_substring):
            shortest = valid_substring
        removed_char = s[left]
        left += 1
        s_freq[removed_char] -= 1
        if s_freq[removed_char] < t_freq[removed_char]:
            have -= 1

Longest Repeating Character Replacement

Sliding window. A window is valid if window_size - max_freq <= k, where max_freq is the count of the most frequent character inside the window. Expand right every iteration, shrink left until the window is valid again.

Use a for loop on the right pointer, not a while loop with manual initialization. Right expands by one each iteration unconditionally — no pre-seeding or off-by-one handling needed.

left = 0
freq = defaultdict(int)
longest = 0

for right in range(len(s)):
    freq[s[right]] += 1
    while (right - left + 1) - max(freq.values()) > k:
        freq[s[left]] -= 1
        left += 1
    longest = max(longest, right - left + 1)

Longest Substring Without Repeating Characters

Sliding window with a hashmap tracking the last seen index of each character. Instead of maintaining an explicit left pointer, track cur_length directly.

char_to_last_seen = {}
longest = 0
# current sliding window length
window_length = 0

for i, c in enumerate(s):
    if c not in char_to_last_seen:
        window_length += 1
    else:
        last_index = char_to_last_seen[c]
        # cap at window_length + 1 in case the duplicate is outside the current window
        window_length = min(i - last_index, window_length + 1)
    char_to_last_seen[c] = i
    longest = max(longest, window_length)

Crux: min(i - last_seen_idx, cur_length + 1): when a duplicate is found, the new window can extend at most to just past the last occurrence (i - last_seen_idx). But if that duplicate is outside the current window, we shouldn't arbitrarily expand — cap at cur_length + 1, which is what you'd get if the character were new.

Decode String

Use a stack where each entry tracks the repeat count and accumulated string for the current nesting level. On [, push a new entry. On ], pop and append the repeated string onto the level below. Initialize with [1, ""] as a base so the outermost string needs no special-casing.

Use a list, not a tuple: storing each entry as [count, string] lets you modify the string in place with stack[-1][1] += c. Tuples are immutable, so you'd have to pop and re-push just to append a character — awkward and easy to flag in an interview.

Multi-digit numbers: accumulate digits with digit = 10 * digit + int(c) and reset to 0 on [.

Copy List with Random Pointer

Approach 1 — Interleaving (O(1) space): weave copies between originals (A → A' → B → B'), set random pointers using node.random.next to reach the copy, then extract the copy list in a third pass. The original list is destroyed in the process.

Approach 2 — Hashmap (O(n) space): map each original node to its copy in one pass, then wire up next and random in a second pass using the map. Cleaner and easier to reason about — looking up the copy of any node is O(1).

Daily Temperatures

Monotonic decreasing stack. For each day, pop any previous days that are cooler than the current temperature — those days have found their answer. The days waiting on the stack are always in decreasing temperature order.

Python has no peek() — use stack[-1] to look at the top of the stack without popping.

You can store just the index on the stack and look up the temperature via temperatures[i], but storing (temp, index) pairs is more readable.

Subarray Sum Equals K

A subarray sum equals prefix_sum[j] - prefix_sum[i]. The brute force checks all pairs — O(n²). The insight: for each position j, you already know exactly what earlier prefix sum you need: prefix[j] - k. If you've seen that value before, every occurrence is a valid subarray.

Running hashmap (like Two Sum): instead of storing the full prefix sum array, maintain a single running sum and a map from prefix sum value to how many times it's appeared. No indices needed — just counts. Add prefix_sum_count[0] = 1 before the loop to handle subarrays starting at index 0.

Target = current prefix sum − k, not k − prefix sum.

Remove Nth Node From End of List

Two pointers: advance fast by n steps first, then move both until fast.next is None. At that point slow is just before the node to remove, so slow.next = slow.next.next.

Edge case — removing the head: if fast is None after the initial loop, n equals the list length, meaning the head itself needs to be removed. Return head.next early. This also guarantees that by the time you reach slow.next = slow.next.next, slow.next is always a real node — never None.

Linked List Cycle

Use two pointers starting at head — slow moves 1 step, fast moves 2. If there's a cycle they're guaranteed to meet. Move before checking (not after) to avoid a false match at the start.

Why they always meet (never skip): each iteration, slow moves +1 and fast moves +2, so the gap between them shrinks by exactly 1. Starting at gap N, after N steps the gap is 0. It can never jump from 2 to 0 and skip over — it decrements by 1 at a time, so they're guaranteed to land on the same node.

Merge Two Sorted Lists

Use a dummy head node so the merged list always has a stable starting point, avoiding special-casing the first node. Walk both lists with a pointer, always attaching the smaller current node and advancing that list's pointer. Once one list runs out, attach the remainder of the other list directly (no need to copy node by node).

Relink, don't copy: attach the existing nodes (cur.next = list1) instead of creating new ListNode copies. Same logic, but O(1) extra space instead of O(n).

def mergeTwoLists(list1, list2):
    dummy_head = ListNode(0)
    cur = dummy_head

    while list1 and list2:
        if list1.val < list2.val:
            cur.next = list1
            list1 = list1.next
        else:
            cur.next = list2
            list2 = list2.next
        cur = cur.next

    if list1:
        cur.next = list1
    if list2:
        cur.next = list2

    return dummy_head.next

Reverse Linked List

Iteratively walk the list, flipping each node's next pointer to point backward. Before overwriting cur.next, save a reference to the next node so you don't lose the rest of the list. Track prev as the new tail of the reversed portion, and at the end prev is the new head. O(n) time, O(1) extra space.

def reverseList(head):
    prev = None
    cur = head

    while cur:
        next_node = cur.next
        cur.next = prev
        prev = cur
        cur = next_node

    return prev

3Sum

Sort the array, then for each fixed first element use two pointers from both ends to find pairs summing to the target. O(N^2) time, O(1) extra space (besides the sort).

Skipping duplicates: the "no duplicate triplets" rule means the duplicate-skip logic only matters after a valid triplet is found. If two_sum != target, nothing was added to the output, so there's nothing to dedupe — just move the pointer and keep searching. Only when two_sum == target do you need to advance past any repeated values for both left and right (and skip duplicates of the outer loop's fixed element too).

Container With Most Water

Two pointers starting at both ends, tracking max area as (right - left) * min(height[left], height[right]). Always move the pointer at the shorter height inward.

Why moving the shorter side is correct: moving the taller pointer can never increase the area, since the width shrinks and the limiting height (the shorter side) stays the same or gets worse. Only moving the shorter pointer has a chance of finding a taller wall that could outweigh the lost width.

Product of Array Except Self

O(1) extra space version: one pass left-to-right tracks a running prefix_product and writes it into output[i] before updating it. A second pass right-to-left tracks a running suffix_product and multiplies it into output[i]. No separate prefix/suffix arrays needed.

Naming tip — name by role, not type: prefix_product / suffix_product describe what the running value represents in the algorithm, versus generic names like products / rev_products which only describe the data type (an array) and force the reader to infer the role.

Valid Palindrome

String manipulation basics:

• ''.join(c for c in s.lower() if c.isalnum()) — a generator expression filters and lowercases each char, and .join() collects the results back into a single string.
• .isalnum() checks if a character is a letter or digit, used here to strip out spaces and punctuation during normalization.
• Strings are indexable like lists (s[i]), which makes the two-pointer comparison straightforward.

Two Sum II - Input Array Is Sorted

Two pointers from both ends, moving inward based on whether the sum is too small or too large. If the true answer is at indices i < j, the pointers can never cross past them: if left already equals i and the sum is still too small, then numbers[right] must already be ≥ numbers[j] (sorted array), forcing the sum ≥ target, a contradiction. So the window only shrinks toward (i, j), never past it, and this only works because the array is sorted.

Lowest Common Ancestor of a Binary Tree

Return None to signal "not found", or the node itself to signal "found something". Early exit when the current node is p or q — safe because the problem guarantees both exist. If both sides return non-None, this node is the LCA. Otherwise bubble up whichever side found something.

def dfs(node):
    if not node:
        return None
    if node == p or node == q:
        return node
    left = dfs(node.left)
    right = dfs(node.right)
    if left and right:
        return node        # p and q on opposite sides
    return left or right  # bubble up whichever side found something

Validate Binary Search Tree

The key insight: don't bubble information up — pass constraints down. Every node has a valid range determined by all its ancestors, not just its immediate parent. Pass an upper and lower bound through the recursion so each node knows exactly what range it must fall in.

Going left: current node's value becomes the new upper bound. Going right: current node's value becomes the new lower bound. Initialize with float('inf') and float('-inf') — prefer these over sys.maxsize, which is a real finite integer and would incorrectly reject a BST node whose value equals it.

def dfs(node, max_value, min_value):
    if not node:
        return True
    if node.val >= max_value or node.val <= min_value:
        return False
    return dfs(node.left, node.val, min_value) and dfs(node.right, max_value, node.val)

return dfs(root, float('inf'), float('-inf'))

Group Anagrams

Hash map where the key is a sorted tuple of characters (or a character-count tuple). All words that are anagrams of each other map to the same key.

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs):
        groups = defaultdict(list)
        for word in strs:
            freq = defaultdict(int)
            for c in word:
                freq[c] += 1
            key = tuple(sorted(freq.items(), key=lambda x: x[0]))
            groups[key].append(word)

        return list(groups.values())

Why tuple(): dict keys must be hashable, and a dict (or list) itself is mutable and unhashable. sorted(freq.items()) produces a list of (char, count) pairs in a canonical order, but it's still a list. Wrapping it in tuple() converts it to an immutable, hashable sequence, so it can be used as the key in groups. The sorting step is what makes anagrams (which have the same character counts in some order) map to the same key.

Course Schedule

Classic Kahn's application. Build a graph of prerequisites, compute in-degrees, BFS from all nodes with in-degree 0. If you process all courses, no cycle exists.

Binary Tree Level Order Traversal

Snapshot len(queue) at the start of each BFS iteration — that count is exactly how many nodes are on the current level. Process only that many nodes before appending the level's result, so children queued during the loop don't bleed into the current level.

for _ in range(len(queue)):  # snapshot: nodes at this level
    node = queue.popleft()
    # children appended here are counted in the NEXT iteration

Binary Tree Right Side View

Use len(queue) to snapshot the current level size and a levelSeen bool to ensure only the first node processed per level gets added to the result. Enqueue node.right before node.left so the rightmost node is always dequeued first.

Number of Islands

Iterate the grid; when you hit a '1', increment the island count and BFS to sink all connected land cells (mark as '0'). Use a queue to explore all 4 neighbors level by level — avoids DFS recursion which can overflow the call stack on large grids.